package org.hw.algorithm.recursion;

/**
 * @Program: demo
 * @Author: hewei
 * @Date: 2024-03-28 11:12
 * @Description: 八皇后递归回溯求解：单数组实现，数组的索引代表行，数组的值代表列
 **/
public class EightQueensOne {
    private static final int SIZE = 8;
    private int[] queens = new int[SIZE]; // 存储每行皇后的列位置
    private int solutions = 0; // 解决方案的数量

    public static void main(String[] args) {
        EightQueensOne eq = new EightQueensOne();
        eq.solve();
        System.out.println("Total solutions: " + eq.solutions);
    }

    public void solve() {
        placeQueen(0); // 从第一行开始放置皇后
    }

    private void placeQueen(int row) {
        if (row == SIZE) {
            // 如果所有皇后都成功放置，打印解决方案并增加计数
            printQueens();
            solutions++;
            return;
        }

        for (int col = 0; col < SIZE; col++) {
            // 尝试在当前行的每一列放置皇后
            if (isValid(row, col)) {
                queens[row] = col; // 放置皇后
                placeQueen(row + 1); // 递归放置下一行的皇后
            }
        }
    }

    private boolean isValid(int row, int col) {
        // 检查当前位置是否有效
        for (int i = 0; i < row; i++) {
            if (queens[i] == col || // 检查列冲突
                    queens[i] - i == col - row || // 检查主对角线冲突
                    queens[i] + i == col + row) { // 检查副对角线冲突
                return false;
            }
        }
        return true;
    }

    private void printQueens() {
        // 打印当前解决方案的棋盘布局
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (queens[i] == j) {
                    System.out.print(" Q "); // 标记皇后的位置
                } else {
                    System.out.print(" . "); // 标记空位置
                }
            }
            System.out.println();
        }
        System.out.println(); // 在每个解决方案之间添加空行分隔
    }
}